#include <stdio.h>

// 递归实现的二分查找函数
int recursiveBinarySearch(int arr[], int low, int high, int key) {
    if (low > high) {
        return -1; // 基本情况，如果low大于high，说明找不到
    }

    int mid = low + (high - low) / 2; // 计算中间索引，防止溢出

    if (arr[mid] == key) {
        return mid; // 如果找到关键字，返回其位置
    } else if (arr[mid] > key) {
        return recursiveBinarySearch(arr, low, mid - 1, key); // 关键字小于中间值，搜索左半部
    } else {
        return recursiveBinarySearch(arr, mid + 1, high, key); // 关键字大于中间值，搜索右半部
    }
}

// 主函数，用于测试递归折半查找
int main() {
    int data[] = {3, 5, 8, 10, 14, 17, 21, 24, 27, 30, 33};  // 一个已排序的数组
    int size = sizeof(data) / sizeof(data[0]);
    int key = 17;  // 我们想要查找的关键字

    int index = recursiveBinarySearch(data, 0, size - 1, key);  // 调用递归折半查找函数

    if (index != -1) {
        printf("Element found at index: %d\n", index);
    } else {
        printf("Element not found.\n");
    }

    return 0;
}
